package com.demo.java.OD51_100.OD63;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【快递运输】问题-动态规划法
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145605565
 */
public class OdMain2 {
    /**
     * 使用动态规划方法来计算符合条件的最大子集数量。
     *
     * @param array    存储数值的数组
     * @param maxValue 允许的最大和
     * @return 最大的符合条件的子集数量
     */
    private static int solve(int[] array, int maxValue) {
        int n = array.length;
        // dp[i] 表示和为 i 时最多能选多少个元素
        int[] dp = new int[maxValue + 1];

        // 初始化 dp 数组
        Arrays.fill(dp, -1);
        dp[0] = 0;  // 和为0时，选取的元素数为0

        // 通过遍历每个元素来更新 dp 数组
        for (int num : array) {
            for (int j = maxValue; j >= num; --j) {
                if (dp[j - num] != -1) {
                    dp[j] = Math.max(dp[j], dp[j - num] + 1);
                }
            }
        }

        // 查找最大和不超过 maxValue 的子集
        int result = 0;
        for (int i = 0; i <= maxValue; i++) {
            if (dp[i] != -1) {
                result = Math.max(result, dp[i]);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        try {
            Scanner s = new Scanner(System.in);
            String[] line = s.nextLine().split(",");
            int maxValue = Integer.parseInt(s.nextLine());
            int[] array = new int[line.length];
            for (int j = 0; j < line.length; ++j) {
                array[j] = Integer.parseInt(line[j]);
            }
            Arrays.sort(array);
            System.out.println(solve(array, maxValue));
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("input error");
        }
    }
}